package danran.regular;

import java.util.*;

/**
 * @Classname MergeTwoLists
 * @Description TODO
 * @Date 2021/10/13 14:17
 * @Created by ASUS
 */
public class MergeTwoLists {

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> q = f(new PriorityQueue<>(Comparator.comparingInt(o -> o.val)), lists);
        ListNode head, cur, next;
        head = q.poll();
        cur = head;
        while (!q.isEmpty()) {
            next = q.poll();
            cur.next = next;
            cur = next;
        }
        if (cur != null) cur.next = null;
        return head;
    }

    public PriorityQueue<ListNode> f(PriorityQueue<ListNode> q, ListNode[] nodeLists) {
        for (ListNode node : nodeLists) {
            ListNode cur = node;
            while (cur != null) {
                q.offer(cur);
                cur = cur.next;
            }
        }
        return q;
    }

    public ListNode mergeTwoLists1(ListNode a, ListNode b) {
        if (a == null) return b;
        if (b == null) return a;
        ListNode t = new ListNode(0);
        ListNode a_p = a, b_p = b, p = t;
        while (true) {
            if (a_p == null) {
                p.next = b_p;
                break;
            }
            if (b_p == null) {
                p.next = a_p;
                break;
            }
            int n1 = a_p.val, n2 = b_p.val;
            if (n1 < n2) {
                p.next = a_p;
                a_p = a_p.next;
                p = p.next;
            } else {
                p.next = b_p;
                b_p = b_p.next;
                p = p.next;
            }
        }
        return t.next;
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        PriorityQueue<ListNode> q = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
        helper(q, a, b);
        ListNode head, cur, next;
        head = q.poll();
        cur = head;
        while (!q.isEmpty()) {
            next = q.poll();
            cur.next = next;
            cur = next;
        }
        if (cur != null) cur.next = null;
        return head;
    }

    public void helper(PriorityQueue<ListNode> q, ListNode... nodeLists) {
        for (ListNode a : nodeLists) {
            ListNode cur = a;
            while (cur != null) {
                q.offer(cur);
                cur = cur.next;
            }
        }
    }

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        List<ListNode> a = new ArrayList<>();// 单数节点集合
        List<ListNode> b = new ArrayList<>();// 偶数节点集合
        int index = 1;
        ListNode p = head, tmp;
        while (p != null) {
            tmp = p;
            p = p.next;
            tmp.next = null;
            if ((index & 1) == 1) {// 放入单数集合
                a.add(tmp);
            } else b.add(tmp);
            index++;
        }
        List<ListNode> t;
        boolean f = false;
        if (a.size() < b.size()) {
            t = a;
            a = b;
            b = t;
            f = true;
        }// 保证a集合的长度>=b的长度
        head = new ListNode(0);
        p = head;
        for (int i = 0; i < b.size(); i++) {
            // 偶数为头
            if (f) {// 发生交换==a为偶数==b为奇数
                p.next = a.get(i);
                p = p.next;
                p.next = b.get(i);
                p = p.next;
            } else { // 没有发生交换
                p.next = b.get(i);
                p = p.next;
                p.next = a.get(i);
                p = p.next;
            }
        }// endfor => p指向最后一个成对的节点
        if (a.size() > b.size()) {
            p.next = a.get(a.size() - 1);
            p.next.next = null;
        }
        return head.next;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        ListNode d = dummy, p = head, t;
        while ((head = moveToK(p, k)) != null) {// 说明还有一段k节点的链表段
            t = head;
            head = head.next;// 下一段的开始
            t.next = null;
            List<ListNode> r = reverse(p);
            d.next = r.get(0);
            r.get(1).next = head;
            d = r.get(1);
            p = head;
        }
        return dummy.next;
    }

    public ListNode moveToK(ListNode startNode, int k) {
        ListNode ans = startNode;
        for (int i = 0; i < k - 1; i++) {
            if (ans != null) ans = ans.next;
            else break;
        }
        return ans;
    }

    public List<ListNode> reverse(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode p = head, t;
        while (p != null) {
            t = p;
            p = p.next;
            t.next = null;
            stack.push(t);
        }
        ListNode dummy = new ListNode(0);
        p = dummy;
        while (!stack.isEmpty()) {
            p.next = stack.pop();
            p = p.next;
        }
        List<ListNode> ans = new ArrayList<>(2);
        ans.add(dummy.next);
        ans.add(p);
        return ans;
    }
}
